package _dp

import org.junit.Assert
import org.junit.Test

/*
 https://leetcode.cn/problems/unique-paths/description/
 https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html

62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

示例 1：
输入：m = 3, n = 7
输出：28

示例 2：
输入：m = 3, n = 2
输出：3

示例 3：
输入：m = 7, n = 3
输出：28

示例 4：
输入：m = 3, n = 3
输出：6
 */
class leetcode_62 {
    @Test
    fun test_1() {
        val actual = uniquePaths(3, 7)
        val expect = 28
        Assert.assertEquals(actual, expect)
    }

    @Test
    fun test_2() {
        val actual = uniquePaths(3, 2)
        val expect = 3
        Assert.assertEquals(actual, expect)
    }

    @Test
    fun test_3() {
        val actual = uniquePaths(7, 3)
        val expect = 28
        Assert.assertEquals(actual, expect)
    }

    @Test
    fun test_4() {
        val actual = uniquePaths(3, 3)
        val expect = 6
        Assert.assertEquals(actual, expect)
    }

    fun uniquePaths(m: Int, n: Int): Int {
        /*
        动态规划
        1 确定数组
        dp[m][n]
        2 确定递推公式：
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
        3 初始化数组
        dp[1 to i][0] = 1
        dp[0][1 to j] = 1
        4 遍历数组
        5 打印结果
        */

        // 1 确定数组：i，j多少路径

        val dp = Array(m) { IntArray(n) } // TODO:
//        val dp: Array<Array<Int>> = Array(m) {
//            Array(n) {
//                0
//            }
//        }

        // 3 初始化数组
        // 初始化第1列
        for (i in 0 until m) {
            dp[i][0] = 1
        }
        // 初始化第1行
        for (j in 0 until n) {
            dp[0][j] = 1
        }


        // 2 确定递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]

        // 4 遍历
        for (i in 1 until m) { // TODO: i < m
            for (j in 1 until n) { // TODO: j < n
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                println(" " + dp[i][j] + "=" + dp[i - 1][j] + " + " + dp[i][j - 1])
            }
        }

        return dp[m - 1][n - 1] // TODO: m-1,n-1
    }
}